function BinarySearchTree() {

    //节点构造函数
    function Node(key, value) {
        this.key = key
        this.value = value
        this.left = null
        this.right = null
    }

    //根属性
    this.root = null

    //插入值
    BinarySearchTree.prototype.insert = function (key, value) {
        let newNode = new Node(key, value)
        if (!this.root) {
            this.root = newNode
        } else {
            this.insertNode(newNode, this.root)
        }
    }

    //插入节点
    BinarySearchTree.prototype.insertNode = function (newNode, node) {
        if (newNode.key > node.key) {
            if (!node.right) {
                node.right = newNode
            } else {
                this.insertNode(newNode, node.right)
            }
        } else {
            if (!node.left) {
                node.left = newNode
            } else {
                this.insertNode(newNode, node.left)
            }
        }
    }

    //先序遍历
    BinarySearchTree.prototype.preOrderTraversal = function (handleNode) {
        this.preOrderTraversalNode(this.root, handleNode)
    }

    //先序遍历节点
    BinarySearchTree.prototype.preOrderTraversalNode = function (node, handleNode) {
        if (node) {
            handleNode(node.key, node.value)
            this.preOrderTraversalNode(node.left, handleNode)
            this.preOrderTraversalNode(node.right, handleNode)
        }
    }
    //中序遍历
    BinarySearchTree.prototype.midOrderTraversal = function (handleNode) {
        this.midOrderTraversalNode(this.root, handleNode)
    }

    //中序遍历节点
    BinarySearchTree.prototype.midOrderTraversalNode = function (node, handleNode) {
        if (node) {
            this.preOrderTraversalNode(node.left, handleNode)
            handleNode(node.key, node.value)
            this.preOrderTraversalNode(node.right, handleNode)
        }
    }

    //后序遍历
    BinarySearchTree.prototype.postOrderTraversal = function (handleNode) {
        this.postOrderTraversalNode(this.root, handleNode)
    }

    //后序遍历节点
    BinarySearchTree.prototype.postOrderTraversalNode = function (node, handleNode) {
        if (node) {
            this.preOrderTraversalNode(node.left, handleNode)
            this.preOrderTraversalNode(node.right, handleNode)
            handleNode(node.key, node.value)
        }
    }

    //key最大值的节点
    BinarySearchTree.prototype.maxKeyNode = function () {
        let node = this.root
        while (node.right) {
            node = node.right
        }
        return node
    }

    //key最小值的节点
    BinarySearchTree.prototype.minKeyNode = function () {
        let node = this.root
        while (node.left) {
            node = node.left
        }
        return node
    }

    //搜索节点
    BinarySearchTree.prototype.searchNode = function (key) {
        let node = this.root
        while (node) {
            if (key > node.key) {
                node = node.right
            } else if (key < node.key) {
                node = node.left
            } else if (key == node.key) {
                return node
            } else {
                throw (`${key}无法与节点的键比较`)
            }
        }
    }

    //删除节点
    BinarySearchTree.prototype.remove = function (key) {
        let current = this.root
        let parent = null
        let isLeftChild = true

        //1.找到该节点
        while (current) {
            if (key > current.key) {
                parent = current
                current = current.right
                isLeftChild = false
            } else if (key < current.key) {
                parent = current
                current = current.left
                isLeftChild = true
            } else if (key == current.key) {
                break
            } else {
                throw (`${key}无法与节点的键比较`)
            }
        }
        console.log(current)
        console.log(parent)
        //2.删除该节点
        if (current) {
            if (current.left == null && current.right == null) {
                console.log(current.key+' 是叶节点')
                //2.1该节点是叶节点
                if (current == this.root) {
                    //2.1.1该节点是根节点
                    this.root = null
                } else {
                    isLeftChild ? parent.left = null : parent.right = null
                }
            } else if (current.left || current.right) {
                //2.2该节点有1个子节点
                console.log(current.key+' 只有一个子节点')
                let childeNode = current.left || current.right
                isLeftChild ? parent.left = childeNode : parent.right = childeNode
            }else{
                //2.2该节点有2个子节点
            }


            
        }
    }
}

let bst = new BinarySearchTree()
bst.insert(11, 'a')
bst.insert(7, 'b')
bst.insert(5, 'c')
bst.insert(3, 'c')
bst.insert(9, 'd')
bst.insert(8, 'e')
bst.insert(10, 'f')
bst.insert(15, 'g')
bst.insert(13, 'h')
bst.insert(12, 'i')
bst.insert(14, 'g')
bst.insert(20, 'g')
bst.insert(18, 'g')
bst.insert(25, 'g')
let res = ''
function handler(key, value) {
    res += key + ','
}
bst.preOrderTraversal(handler)
console.log(res)

bst.remove(5)

// let res1 = ''
// function handler(key, value) {
//     res1 += key + ','
// }
// bst.preOrderTraversal(handler)
// console.log(res1)

